Computers have proliferated into all aspects of society and in today's increasingly competitive market-place, the performance of not only the machines themselves but also the software that runs on these machines, is of the utmost importance. Software developers are therefore continually looking for methods to improve the execution efficiency of the code (programs) they produce in order to meet the high expectations of software users.
One such method is by inserting pre-execution instructions into source code such that execution of such instructions cause a portion of the program defined by the source code to be pre-executed. This is described in US Patent Application Publication US 2002/0055964.
Further, US Patent Application Publication US 2002/0144083 describes a processor using spare hardware contexts to spawn speculative threads such that data is pre-fetched in advance of a main thread.
Another known method is “branch prediction” (also mentioned in US 2002/0055964). Within a program there are typically a number of branch points. These are points which can return one of a finite number of results. Prediction techniques are used to determine the likely return result such that a branch point's subsequent instructions can be pre-executed on this assumption. “if . . . else” statements and “case” statements are two well known examples of branch points.
There are a number of branch prediction techniques known in the industry. Such techniques are common in RISC and processor architectures (e.g. The pSeries architecture).
See alsowww.mtl.t.u-tokyo.ac.jp/˜niko/Downloads/chitaka-EuroPar 2001-PerThreadPredictor.pdf which presents a hardware scheme for improving branch prediction accuracy.
Software schemes also exist. A paper “Static Correlated Branch Prediction” by Cliff Young and Michael D Smith (ACM Transactions on Programming Languages and Systems, Vol. 21. No ?, ??? 1999, Pages 111-159) describes how the repetitive behaviour in the trace of all conditional branches executed by a program can be exploited by a compiler. Another paper “A Comparative Analysis of Schemes for Correlated Branch Prediction” by Cliff Young, Michael D Smith and Nicholas Gloy (published in the Proceedings of the 22nd Annual International Symposium on Computer Architecture, June 1995) presents a framework that categorizes branch prediction schemes by the way in which they partition dynamic branches and by the kind of predictor they use.
The paper “Understanding Backward Slices of Performance Degrading Instructions” by C Zilles and G Sohi (published in the proceedings of the 27th Annual International Symposium on Computer Architecture (ISCA-2000), Jun. 12-14, 2000) discusses the small fraction of static instructions whose behaviour cannot be anticipated using current branch predictors and caches. The paper analyses the dynamic instruction stream leading up to these performance degrading instructions to identify the operations necessary to execute them early.
Another paper “The Predictability of Computations that Produce Unpredictable Outcomes” by T Aamodt, A Moshovos and P Chow (an update of the paper that appeared in the Proceedings of the 5th Workshop on Multithreaded Execution, Architecture, and Compilation—pages 23-34, Austin, Tex., December 2001) studies the dynamic stream of slice traces that foil existing branch predictors and measures whether these slices exhibit repetition.
“Speculative Data-Driven Multithreading” by Amir Roth and Gurindar Sohi (appearing in the Proceedings of the 7th International Conference on High Performance Computer Architecture (HPCA-7), Jan. 22-24, 2001) describes the use of speculative data-driven multithreading (DDMT) for coping with mispredicted branches and loads that miss in the cache.
It is also known for the programmer to be able to provide branch prediction pragma—see http://www.geocrawler.com/archives/3/357/1993/7/0/1992785/.
Whilst branch prediction techniques are known, there is however a need in the industry for more efficient processing of software functions as opposed to branch points.